The advent of networks, and the Internet in particular, have resulted in on-line services becoming commonplace. Such on-line services are generally accessed via some form of messaging over a network. A sustained exchange of related messages between two parties generally requires that the parties maintain historical information about the conversation (conversation state) and that the parties have a mechanism for identifying messages that may are related.